package pro.softzhang.algo.lc700;

import pro.softzhang.algo.flag.knowledge.KGraph;

import java.util.LinkedList;
import java.util.Queue;

/**
 *
 */
@KGraph
public class LC733_FloodFill {
    public static void main(String[] args) {

    }

    static class Solution {
        public int[][] floodFill(int[][] image, int sr, int sc, int color) {
            int current = image[sr][sc];
            if (current == color) {
                return image;
            }

            int[] dx = {1, 0, 0, -1}, dy = {0, 1, -1, 0};
            int n = image.length, m = image[0].length;
            Queue<int[]> q = new LinkedList<>();
            q.offer(new int[]{sr, sc});
            image[sr][sc] = color;
            while (!q.isEmpty()) {
                int[] c = q.poll();
                int x = c[0], y = c[1];
                for (int i = 0; i < 4; i++) {
                    int mx = x + dx[i], my = y + dy[i];
                    if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == current) {
                        q.offer(new int[]{mx, my});
                        image[mx][my] = color;
                    }
                }
            }
            return image;
        }
    }
}
